package 面试经典150题.图;

/**
 * @author tmh
 * @date 2024/6/27 20:54
 * @description
 */
public class T130被围绕的区域 {
    class Solution {
        public void solve(char[][] board) {
            if (board == null || board.length == 0) return;
            int m = board.length;
            int n = board[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 从边缘o开始搜索
                    boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                    if (isEdge && board[i][j] == 'O') {
                        dfs(board, i, j);
                    }
                }
            }
/*           这道题我们拿到基本就可以确定是图的 dfs、bfs 遍历的题目了。题目中解释说被包围的区间不会存在于边界上，所以我们会想到边界上的 O 要特殊处理，
            只要把边界上的 O 特殊处理了，那么剩下的 O 替换成 X 就可以了。问题转化为，如何 寻找和边界联通的 O，
            这时候的 O 是不做替换的。因为和边界是连通的。为了记录这种状态，我们把这种情况下的 O 换成 # 作为占位符，待搜索结束之后，
            遇到 O 替换为 X（和边界不连通的 O）；遇到 #，替换回 O(∗∗和边界连通的O$**)。

            作者：Xdims
            链接：https://leetcode.cn/problems/surrounded-regions/solutions/6067/bfsdi-gui-dfsfei-di-gui-dfsbing-cha-ji-by-ac_pipe/
            来源：力扣（LeetCode）
            著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    if (board[i][j] == '#') {
                        board[i][j] = 'O';
                    }
                }
            }
        }

        public void dfs(char[][] board, int i, int j) {
            if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') {
                // board[i][j] == '#' 说明已经搜索过了.
                return;
            }
            board[i][j] = '#';
            dfs(board, i - 1, j); // 上
            dfs(board, i + 1, j); // 下
            dfs(board, i, j - 1); // 左
            dfs(board, i, j + 1); // 右
        }
    }
}
